#define _CRT_SECURE_NO_WARNINGS

#include<iostream>
#include<cstring>
#include<cstring>
using namespace std;

const int mod = 1000000007;

typedef struct
{
   int weight;
   int parent, lchild, rchild;
}HTNode, * HuffmanTree; // 哈夫曼树

//调整
void Select(HuffmanTree HT, int len, int& s1, int& s2)
{
   int i, flag = 0;
   for (i = 1; i <= len; i++)
   {
       if (flag == 0 && HT[i].parent == 0)
       {
           s1 = i; flag = 1;
       }
       if (flag == 1 && HT[i].weight < HT[s1].weight && HT[i].parent == 0)
       {
           s1 = i;
       }
   }
   for (i = 1; i <= len; i++)
   {
       if (flag == 1 && HT[i].parent == 0 && i != s1) // 防止最小值和次小值相同
       {
           s2 = i; flag = 0;
       }
       if (flag == 0 && HT[i].weight < HT[s2].weight && HT[i].parent == 0 && i != s1)
       {
           s2 = i;
       }
   }
}

//创建哈夫曼树
void CreatHuffmanTree(HuffmanTree& HT, int n)
{
   int m, s1, s2, i;
   if (n <= 1)return;
   m = 2 * n - 1;                
   HT = new HTNode[m + 1];       
   for (i = 1; i <= m; ++i)           
   {
       HT[i].parent = HT[i].lchild = HT[i].rchild = 0;
   }
 
   for (i = 1; i <= n; ++i) cin >> HT[i].weight;

   for (i = n + 1; i <= m; ++i)
   { 
       Select(HT, i - 1, s1, s2);

       HT[s1].parent = i;
       HT[s2].parent = i;

       HT[i].lchild = s1;
       HT[i].rchild = s2;                          
       HT[i].weight = (HT[s1].weight + HT[s2].weight) % mod;
   }                                             
}                                                 


//计算最短路径
int countWPL(HuffmanTree HT, int n) 
{
   int i, sum = 0;
   for (i = n + 1; i <= 2 * n - 1; i++) 
   {
       sum = (sum + HT[i].weight) % mod;
   }
   return sum % mod;
}

int main()
{
   ios::sync_with_stdio(0);
   cin.tie(0);
   cout.tie(0);
   int n;
   while (cin >> n) 
   {
       HuffmanTree HT;
       CreatHuffmanTree(HT, n);
       cout << countWPL(HT, n) << "\n";
   }
  
   return 0;
}


 
//#include <iostream>
//#include <queue>
//#include <algorithm>
//#include <cstring>
//
//using namespace std;
//
//typedef long long LL;
//
//const int mod = 1000000007;
//const int N = 1e5+10;
//
//
//void WPL(LL a[],int n )
//{
//	int cnt = 0;
//	priority_queue<LL,vector<LL>,greater<LL>> q;
//	for (int i = 0; i < n; i++) q.push(a[i]);
//	while (q.size() >= 2)
//	{
//		LL num1 = q.top();
//		q.pop();
//		LL num2 = q.top();
//		q.pop();
//		LL x = num1 + num2;
//		cnt = (cnt + x) % mod;
//		q.push(x); //入队列
//	}
//	cout << (cnt + mod) % mod << endl;
//}
//
//int main()
//{
//	int n;
//	while (cin >> n)
//	{
//		LL a[N];
//		for (int i = 0; i < n; i++) cin >> a[i];
//		WPL(a,n);
//	}
//}